
#define SUCCESS 1
#define FAILURE 0
#define OK 2
#define OUTOFINDEX 0
#define TRUE 3
#define FALSE -3
#define ERROR 0

typedef int Status;
typedef int ElemSet;

typedef struct LNode{
	ElemSet data;
	struct LNode *next;
}LNode,*LinkList;


//*******************循环链表；********************************

Status InitL2(LinkList* L,int *s,int len){
	*L=(struct LNode*)malloc(sizeof(LNode));
	if (*L==NULL) return SUCCESS;
	(*L)->next=NULL;
	struct LNode *p,*q;
	p=*L;
    int i;
	for(i=0;i<len;i++){
		q=(struct LNode*)malloc(sizeof(LNode));
		q->data=s[i];
		q->next=NULL;
		p->next=q;
		p=q;
	}
	return SUCCESS;
}
Status InitList(LinkList* LN,int* str,int len){
	LinkList r,p;
	*LN=(LinkList)malloc(sizeof(LNode));
	if(*LN==NULL) return FAILURE;
	r=*LN;
	r->data=-1;
	r->next=r;
	int i;
	for(i=len;i>0;i--){
		p=(LinkList)malloc(sizeof(LNode));
		if(p==NULL) return FAILURE;
		p->data=str[i-1];
		p->next=r->next,r->next=p;
	}
	return SUCCESS;
}


Status DestoryList(LinkList L){
	LinkList r=L->next,p=r->next;
	while(p!=L) {
		free(r);
		r=p;
		p=p->next;
	}
	free(L);
	return SUCCESS;
}

Status ClearList(LinkList L){
	LinkList p=L->next,r=p->next;
	while(r!=NULL){
		free(p);
		p=r;
		r=r->next;
	}
	free(p);
	L->next=NULL;
	return SUCCESS;
}

Status ListEmpty(LinkList L){
	if(L->next==NULL) return TRUE;
	return FALSE;
}

int ListLength(LinkList L){
	int len=0;
	LinkList p=L->next;
	while(p!=L){
		len++;
		p=p->next;
	}
	return len;
} 


//L为链表任意元素的指针，i为往下第几个元素，e为返回目标元素的值，返回值是目标元素在链表中的位序；
//此函数可以用来定位某元素的下 i 个元素的位置并返回他的值；若L为头指针，则是定位链表的第几个元素
int GetElem(LinkList L,int i,ElemSet* e){
	LinkList p,r,q;
	p=r=L;
	while(r->data!=-1){
			r=r->next;
		}

	if(p->data==-1) p=p->next;
	for(int j=1;j<i;j++){
		p=p->next;
		if(p->data==-1) p=p->next;
	}
	*e=p->data;

	int index=1;
	q=r->next;
	while(q!=p){
		index++;
		q=q->next;
	}

	return index;
}

//L是头指针，i 是元素在链表的位置，用于定位元素，即返回此位置元素的指针；
LinkList GetPointer(LinkList L,int i){
	LinkList p=L->next;
	int j=1;
	while(p!=L && j++<i){
		p=p->next;
	}
	return p;
}

int LocatElem(LinkList L,ElemSet e){
	int index=0;
	LinkList p=L->next;
	while(p!=L && ++index){
		if(p->data==e) return index;
		p=p->next;
	}
	return ERROR;
}

Status PriorElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=L){
		if(r->data==cur_e) return p->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status NextElem(LinkList L,ElemSet cur_e,ElemSet* e){
	LinkList r,p=L->next;
	r=p->next;
	while(r!=L){
		if(p->data==cur_e) return r->data;
		p=r;
		r=r->next;
	}
	return ERROR;
}

Status ListInsert(LinkList L,int i,ElemSet e){

	int len=0,index=1;
	LinkList p=L->next;
	while(p!=L){
		len++;
		p=p->next;
	}
	if(i>len) return OUTOFINDEX;

	LinkList r;
	p=L;
	while(p!=L && ++index<i){
		p=p->next;
	}
	if(p==L || index>i && index==1) return FAILURE;
	r=(LinkList)malloc(sizeof(LNode));
	r->data=e;
	r->next=p->next;
	p->next=r;
	return SUCCESS;
}

Status ListDelete(LinkList L,int i,ElemSet* e){
	LinkList r,p=L->next;
	if(i==1) {
		L->next=p->next;
		free(p);
		return SUCCESS;
	}

	int j=1;
	while(p!=L && ++j<i){
		p=p->next;
	}
	if(p==L && j>i) return FAILURE;
	r=p->next;
	p->next=r->next;
	*e=r->data;
	free(r);
	return SUCCESS;
	
}

int ListTravese(LinkList L,int (*FUNC)(LinkList L,ElemSet e)){
	LinkList p=L->next;
	while(p!=L){
		if(!(*FUNC)(L,p->data)) return FAILURE;
		p=p->next;
	}
	return SUCCESS;

}

//对链表元素进行排序，L为头指针，ch为排序选择，非负为升序，负数为降序；
Status sort(LinkList L,int ch){
	LinkList r,p=L->next;
	ElemSet e;
	p=L->next,r=p->next;

	if(ch>=0){
		while(p->next!=NULL){
			while(r!=NULL){
				if(p->data > r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;
	}
	else while(p->next!=NULL){
			while(r!=NULL){
				if(p->data < r->data) {
					e=p->data;
					p->data=r->data;
					r->data=e;
				}
				r=r->next;
			}
			p=p->next;
			r=p->next;
		}
		return SUCCESS;

}

Status ToString(LinkList L,char* str){
	LinkList p=L->next;
	if(p==NULL) return FAILURE;
	sprintf(str,"%c ",'[');
	while(p!=NULL){
		sprintf(++(++str),"%d,",p->data);
		p=p->next;
	}
	sprintf(++str,"%c",']');
}

//合并两个链表到第三个新的链表里
Status merger(LinkList la,LinkList lb,LinkList* lc){
	*lc=(LinkList)malloc(sizeof(LNode));
	(*lc)->next=NULL;
	LinkList pa=la->next;
	LinkList pb=lb->next;
	LinkList pc=*lc;

	while(pa!=la && pb!=lb){
		if(pa->data < pb->data){
		 pc->next=pa;
		 pc=pa;
		 pa=pa->next;
		}
		else{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}

	}
    if(pa==la) pc->next=pb;
    else pc->next=pa;
    la->next=NULL;
    lb->next=NULL;

	
	return SUCCESS;
}

